package com.ryujung.greedy;

class Solution122 {
    /**
     * 想法1：
     * dp[i][j]代表i买进，j卖出时的收益，该想法是错的，因为这样默认只交易一次，
     * 实际上在一段时间内，可以多次进行买进和卖出的操作，从而达到利益最大化
     * <p>
     * 改进：
     * dp[i][0]表示第i天不持有股票的收益(不持有可以是没有买,也可以是卖出)
     * dp[i][1]表示第i天买进时的收益
     * <p>
     * 最终需要求解dp[prices.length-1][0] 的值
     * 然后每一步都根据股价，进行买进或者步不买，从而利益最大化。
     * <p>
     * 想法2:
     * 遍历数组，只要当前price大于前一天就买进，否则就不买，
     * 也就是直接取所有的上升序列，然后计算差值
     */
    public int maxProfit00(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            // 今天不持有的最大收益，最大值：1昨天未持有股票时的收益，2.昨天持有股票时的收益+今天的股价
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 今天持有股票的最大收益，最大值：1.昨天未持有股票的收益-今天的股价，2.昨天持有股票
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][0];
    }

    /**
     * 解答成功:
     * 执行耗时:1 ms,击败了83.44% 的Java用户
     * 内存消耗:41.6 MB,击败了26.47% 的Java用户
     * 凭数学直觉，取所有的上升序列相加
     */
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            int priceDiff = prices[i] - prices[i - 1];
            max += Math.max(priceDiff, 0);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution122 s = new Solution122();
        System.out.println("answer: 7");
        System.out.println(s.maxProfit00(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(s.maxProfit00(new int[]{1}));
    }
}